package panda.client.engine;

import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;

/**
 * I was too lazy to implement the shuffle function for bins, so I ripped out the required 
 * functions from Collections.shuffle and put it here =P  java.util.Random is replaced by
 * ((int) Math.Random) * i
 * @author zane.tian@gmail.com
 */
public class PandaCollections {
	private static final int SHUFFLE_THRESHOLD = 1;

	// Suppresses default constructor, ensuring non-instantiability.
	private PandaCollections() {}

	/**
	 * Randomly permute the specified list using the specified source of randomness. All permutations occur with equal
	 * likelihood assuming that the source of randomness is fair.
	 * <p>
	 * 
	 * This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a
	 * randomly selected element into the "current position". Elements are randomly selected from the portion of the list
	 * that runs from the first element to the current position, inclusive.
	 * <p>
	 * 
	 * This method runs in linear time. If the specified list does not implement the {@link RandomAccess} interface and
	 * is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled
	 * array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential
	 * access" list in place.
	 * 
	 * @param list
	 *           the list to be shuffled.
	 *           the source of randomness to use to shuffle the list.
	 * @throws UnsupportedOperationException
	 *            if the specified list or its list-iterator does not support the <tt>set</tt> operation.
	 */
	@SuppressWarnings("all")
	public static void shuffle(List<?> list) {
		int size = list.size();
		if(size < SHUFFLE_THRESHOLD) {
			for(int i = size; i > 1; i--) {
				int randomIntInRange = (int) (Math.random() * i);
				swap(list, i - 1, randomIntInRange);
			}
		} else {
			Object arr[] = list.toArray();

			// Shuffle array
			for(int i = size; i > 1; i--) {
				int randomIntInRange = (int) (Math.random() * i);
				swap(arr, i - 1, randomIntInRange);				
			}

			// Dump array back into list
			ListIterator it = list.listIterator();
			for(int i = 0; i < arr.length; i++) {
				it.next();
				it.set(arr[i]);
			}
		}
	}

	/**
	 * Swaps the elements at the specified positions in the specified list. (If the specified positions are equal,
	 * invoking this method leaves the list unchanged.)
	 * 
	 * @param list
	 *           The list in which to swap elements.
	 * @param i
	 *           the index of one element to be swapped.
	 * @param j
	 *           the index of the other element to be swapped.
	 * @throws IndexOutOfBoundsException
	 *            if either <tt>i</tt> or <tt>j</tt> is out of range (i &lt; 0 || i &gt;= list.size() || j &lt; 0 ||
	 *            j &gt;= list.size()).
	 * @since 1.4
	 */
	@SuppressWarnings("all")
	public static void swap(List<?> list, int i, int j) {
		final List l = list;
		l.set(i, l.set(j, l.get(i)));
	}

	/**
	 * Swaps the two specified elements in the specified array.
	 */
	private static void swap(Object[] arr, int i, int j) {
		Object tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}